#Diseño de la red de transporte - Ejercicio 5 (1º Parcial)
#Guastavino Mariano

class Arista:
	def __init__(self, estacionDestino, distancia=0):
		self.__estacionDestino = estacionDestino
		self.__distancia=distancia
        
	def getEstacionDestino(self): 
		return self.__estacionDestino
    
	def getDistancia(self):
		return self.__distancia

class Estacion:
	def __init__(self, dato, posicion=0):
		self.__dato = dato
		self.__posicion=posicion
		self.__listaDeAdyacentes= []

	def getDato(self):
		return self.__dato
    
	def setDato(self, dato): 
		self.__dato = dato
    
	def getPosicion(self): 
		return self.__posicion
    
	def setPosicion(self, posicion):
		self.__posicion=posicion
    
	def getListaDeAdyacentes(self): 
		return self.__listaDeAdyacentes
    
	def conectateCon(self, destino, distancia):
		arista = Arista(destino, distancia)
		self.__listaDeAdyacentes.append(arista)




    
class Red:
	def __init__(self):
		self.__listaDeEstaciones= []
    
	def agregarEstacion(self, estacion):
		estacion.setPosicion(len(self.__listaDeEstaciones))
		self.__listaDeEstaciones.append(estacion)
    
	def eliminarEstacion(self, estacion): 
		self.__listaDeEstaciones.remove(estacion)        
    
	def conectar(self,  origen,  destino,  distancia): 
		origen.conectateCon(destino, distancia)      
    
	def getListaDeEstaciones(self):#Retorna la lista con todos los vertices del grafo.
		return self.__listaDeEstaciones
   
   
	def dfs(self, origen, destino):
		visitados = []
		for i in self.getListaDeEstaciones():
			visitados.append(False)
		mejorcamino = [[],99999]
		camino=[]

		
		self.__dfs(origen,destino, visitados, camino, 0,mejorcamino)
		
		return mejorcamino[0]
	   
	def __dfs(self, origen, destino , visitados, camino, costo,mejorcamino):
		
		visitados[origen.getPosicion()] = True
		adjs = origen.getListaDeAdyacentes()
		camino.append(origen)

		if origen==destino:

			if costo<mejorcamino[1]:

				mejorcamino[0]=[]
				for i in camino:
					mejorcamino[0].append(i)

				mejorcamino[1]=costo

		else:
			for i in adjs:
				if visitados[i.getEstacionDestino().getPosicion()] == False:
					costo=costo+i.getDistancia()
								
					self.__dfs(i.getEstacionDestino(),destino, visitados,camino,costo,mejorcamino)
					costo=costo-i.getDistancia()	
					
		visitados[origen.getPosicion()] = False
		del camino[-1]
		return mejorcamino


        
red = Red()

e1 = Estacion('A',0)
e2 = Estacion('B',1)
e3 = Estacion('C',2)
e4 = Estacion('D',3)
e5 = Estacion('E',4)
e6 = Estacion('F',5)

red.agregarEstacion(e1)
red.agregarEstacion(e2)
red.agregarEstacion(e3)
red.agregarEstacion(e4)
red.agregarEstacion(e5)
red.agregarEstacion(e6)
	
red.conectar(e1, e2, 50)
red.conectar(e1, e3, 20)
red.conectar(e1, e6, 100)

red.conectar(e2, e1, 50)
red.conectar(e2, e3, 20)
red.conectar(e2, e4, 30)

red.conectar(e3, e1, 20)
red.conectar(e3, e2, 20)
red.conectar(e3, e6, 150)

red.conectar(e6, e1, 100)
red.conectar(e6, e3, 150)
red.conectar(e6, e4, 10)
red.conectar(e6, e5, 15)

red.conectar(e4, e2, 30)
red.conectar(e4, e5, 10)
red.conectar(e4, e6, 10)

red.conectar(e5, e4, 10)
red.conectar(e5, e6, 15)




origen=e1
destino=e5


print ("")
print ("El mejor camino entre " + origen.getDato() + " y " + destino.getDato() + " es:")
mejor=red.dfs(origen,destino)
camino=""
for i in mejor:
	camino=camino + i.getDato() + " "
print (camino)
